package rumen.yi;

import java.util.Scanner;


public class yi {
    public static void main(String[] args) {

    }

    public static void swap(int[] arr,int i,int j) { //交换arr i,j 位置上的值
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    public static void selectionSort(int[] arr) { //选择排序
        if(arr == null || arr.length < 2) return;
        for (int i = 0; i <arr.length-1 ; i++) { //i~N+1
            int minIndex=i;
            for (int j = i+1; j <arr.length ; j++) { //i~N+1上找出最小值的下标
                minIndex=arr[j]<arr[minIndex]?j:minIndex;
            }
            swap(arr,i,minIndex);
        }
    }

    public static void bubbleSort(int[] arr) { //冒泡排序
        if(arr==null||arr.length<2) return;
        for (int i = arr.length-1; i > 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
            }
        }
    }

    //一个面试题：现有三种数字，两种出现偶数次，一种出现基数次，问：出现基数次的数字是？
    //^（亦或）的运算规律理解：@一：该位上，相同取0不同取1；@二：不进位加法；
    //^满足交换律，结合律;  0^a = a ; a^a = 0;
    public static void printOddTimesNumber1(int[] arr) {
        int eor=0;
        for (int i = 0; i <arr.length ; i++) {
            eor^=arr[i];
        }
        System.out.println(eor);
    }


    //再一个面试题：四种数字，两种出现基数次，两种出现偶数次，问出现基数次的两个数分别是？
    public static void printOddTimesNumber2(int[] arr) {
        int eor=0;
        for (int i = 0; i <arr.length ; i++) {
            eor^=arr[i];
            //此时eor=a^b;
            //取出eor二进制中最右边的一个1；此位置上a,b必然一个是0，一个是1；
            int rightOne=eor&(~eor+1);
            for (int j = 0; j < arr.length ; j++) {
                
            }
        }

    }

    

}
